#include <stdio.h>
#include <stdlib.h>

/*
 * 循环双向链表
 */

struct list 
{
  int num;
  struct list * prev;
  struct list * next;
};

struct list * create_head()
{
  struct list * head;

  head = (struct list *) malloc (sizeof(struct list));
  head->prev = head;
  head->next = head;

  printf("head->prev:head->next: %p:%p:%p\n", head, head->prev, head->next);
  return head;
}

int insert(struct list * head, int value)
{
  struct list * src, * des;

  if (head == NULL)
    return 0;

  src = head->next;
  printf("src:head->next: %p:%p:%p\n", src, head->prev, head->next);
  des = (struct list *) malloc (sizeof(struct list));
  des->num = value;

  des->next = src;	// 新节点next指向头节点,形成循环
  printf("des:des->next:src: %p:%p:%p\n", des, des->next, src);

  des->prev = head;
  printf("des:des->prev:head: %p:%p:%p\n", des, des->prev, head);

  head->next = des;
  printf("head:head->next:des: %p:%p:%p\n", head, head->next, des);

  src->prev = des;
  printf("src:src->prev:des: %p:%p:%p\n", src, src->prev, des);
}

void display_next(struct list * head)
{
  struct list * src;

  src = head;
  while (src->next != head) {
    src = src->next;
    printf(" %d ", src->num);
  }
  printf("\n");
}

void display_prev(struct list * head)
{
  struct list * src;

  src = head;
  while (src->prev != head) {
    src = src->prev;
    printf(" %d ", src->num);
  }
  printf("\n");
}

struct list * find(struct list * head, int value)
{
  struct list * src;

  if (head->num == value)
    return head;

  src = head->next;
  while (src != head) {
    if (src->num == value)
      return src;
    src = src->next;
  }
  
  return NULL;
}

void delete(struct list * head, int value)
{
  struct list * src, * prev, * next;
  
  src = find(head, value);
  if (src == NULL)
    return;
  
  prev = src->prev;
  next = src->next;

  prev->next = src->next;
  next->prev = src->prev;

  free(src);
}

int main()
{
  struct list * node;

  node = create_head();
  insert(node, 1);
  insert(node, 2);
  insert(node, 3);
  insert(node, 4);
  insert(node, 5);
  display_next(node);
  display_prev(node);
  delete(node, 3);
  display_next(node);
  display_prev(node);
  
}

